#include<iostream>
#include<ctime>
#include<algorithm>
const int threshold = 16;// 分割阈值
void sort(int *first, int *last); //排序算法入口
void introSort(int *first, int *last, int &depthLimits);//内省式排序
void finalSort(int *first, int *last);//最后处理小于16的区间
int *unguardedPartition(int *first, int *last, int pivot);//分割算法，也就是快速排序
int getMedian(const int &a, const int &b, const int &c);//三点中值法找基准
int getDepthLimits(const int *first, const int *last);//2*lgN 找最大递归深度

//插入排序相关
void inserationSort(int *firat, int *last);//直接插入排序
void unguardedInserationSort(int *firat, int *last);//封装unguarded_linear_insert
void linearInsert(int *first, int value, int n);//线性插入，直接插在第一个位置
void unguardLinearInsert(int *last, int value);//无判断，插入

//堆排序相关
void makeHeap(int *first, int n);
void heapify(int *first, int parent, int n);
void heapSort(int *first, int n);

void sort(int *first, int *last) {
  //排序算法入口
  int depthLimits = getDepthLimits(first, last);// 求最大递归深度
  introSort(first, last, depthLimits);//内省排序
  finalSort(first, last);//最后处理大小为16的区块
}
int main() {
  int array[100];

  sort(array, array + 100);

  return 0;
}

void introSort(int *first, int *last, int &depthLimits) {
  //内省排序
  while (last - first > threshold) {
    if (depthLimits == 0) {
      heapSort(first, last - first);
      return;
    }
    --depthLimits;

    int pivot = getMedian(*first, *(first + (last - first) / 2), *(last - 1));
    int *cut = unguardedPartition(first, last, pivot);

    introSort(cut, last, depthLimits);
  }

}
void finalSort(int *first, int *last) {
  //最后处理小于16的区间
  if (last - first > 16) {
    inserationSort(first, first + threshold);
    unguardedInserationSort(first + threshold, last);
  }
  inserationSort(first, last);
}
int *unguardedPartition(int *first, int *last, int pivot) {
  //分割算法，也就是快速排序
  auto swap = [](int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
  };

  while (true) {
    while (*first < pivot) ++first;
    --last;
    while (*last > pivot) --last;

    if (first >= last) return first;
    swap(first, last);
    ++first;
  }
}
int getMedian(const int &a, const int &b, const int &c) {
  //三点中值法找基准
  auto max = [](int a, int b) {
    if (a > b) return a;
    return b;
  };

  int maxNum = max(a, max(a, b));

  if (maxNum == a) return max(b, c);
  if (maxNum == b) return max(a, c);
  if (maxNum == c) return max(a, b);

  return 0;
}

int getDepthLimits(const int *first, const int *last) {
  //2*lgN 找最大递归深度
  int ans = 0, distance = last - first;
  while (distance >= 1) {
    distance >>= 1;
    ans++;
  }

  return ans;
}
void inserationSort(int *first, int *last) {
  //直接插入排序
  for (int *i = first + 1; i != last; i++) {
    linearInsert(first, *i, i - first);
  }
}
void unguardedInserationSort(int *first, int *last) {
  //封装unguarded_linear_insert
  for (int *i = first; i != last; i++) {
    unguardLinearInsert(i, *i);
  }
}
void linearInsert(int *first, int value, int n) {
  if (value <= *first) {
    std::copy(first, first + n, first + 1);
    *first = value;
  } else {
    unguardLinearInsert(first + n, value);
  }
}
void unguardLinearInsert(int *last, int value) {
  //算是插入排序吧
  int *next = last - 1;//next指向最后一个元素

  while (value < *next) {
    *last = *next;
    last = next;
    --next;
  }

  *last = value;
}

void makeHeap(int *first, int n) {
  //构建大顶堆
  for (int i = (n - 1) / 2; i >= 0; i--) {
    heapify(first, i, n);
  }
}
void heapify(int *first, int parent, int n) {
  //堆化
  int left = 2 * parent + 1, right = 2 * parent + 2;
  int max = parent;

  if (left < n && first[left] > first[max]) {
    max = left;
  }
  if (right < n && first[right] > first[max]) {
    max = right;
  }

  auto swap = [](int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
  };

  if (max != parent) {
    swap(&first[max], &first[parent]);
    heapify(first, max, n);
  }
}
void heapSort(int *first, int n) {
  //堆排序
  makeHeap(first, n);

  auto swap = [](int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
  };

  for (int i = n; i > 1; i--) {
    swap(first, first + i - 1);
    heapify(first, 0, i - 1);
  }
}
